package String.easy;

import com.sun.javafx.stage.StageHelper;

import java.util.*;

/**
 * 1. 问题描述
 *      如果字符串满足一下条件之一，则可以称之为 有效括号字符串（valid parentheses string，可以简写为 VPS）：
 *      字符串是一个空字符串 ""，或者是一个不为 "(" 或 ")" 的单字符。
 *      字符串可以写为 AB（A 与 B 字符串连接），其中 A 和 B 都是 有效括号字符串 。
 *      字符串可以写为 (A)，其中 A 是一个 有效括号字符串 。
 *      类似地，可以定义任何有效括号字符串 S 的 嵌套深度 depth(S)：
 *
 *      depth("") = 0
 *      depth(C) = 0，其中 C 是单个字符的字符串，且该字符不是 "(" 或者 ")"
 *      depth(A + B) = max(depth(A), depth(B))，其中 A 和 B 都是 有效括号字符串
 *      depth("(" + A + ")") = 1 + depth(A)，其中 A 是一个 有效括号字符串
 *      例如：""、"()()"、"()(()())" 都是 有效括号字符串（嵌套深度分别为 0、1、2），而 ")(" 、"(()" 都不是 有效括号字符串 。
 *      给你一个 有效括号字符串 s，返回该字符串的 s 嵌套深度 。
 *
 *      分析算法实现：
 *         设置一个全局变量max用于记录s的括号的最大深度
 *         创建一个栈stack用于括号的进出：
 *             如果当前字符为'(':进栈
 *             如果当前字符为')':出栈，如果是出栈说明此时有一个括号匹配，max++
 *                 直到当前字符不是')',停止出栈，此时max记录的是当前s的子串的
 *                 最大深度，但未必是整个s的最大深度
 *
 *         实际上我们不需要关注字符串中的其他字符，我们仅仅将注意力放在括号上即可
 *         对于上述的测试例子我们将括号从字符串中抽象出来: (1+(2*3)+((8)/4))+1
 *             (()(()))
 *         根据逻辑走一遍流程： 进栈 1      出栈 0
 *              创建一个辅助栈 stack = [];
 *              [(]       1
 *              [(,(]     1 1
 *              [(,]      1 1 0
 *              [(,(,]    1 1 0 1
 *              [(,(,(]   1 1 0 1 1
 *              [(,(,]    1 1 0 1 1 0
 *              [(,]      1 1 0 1 1 0 0
 *              []        1 1 0 1 1 0 0 0   所以最大深度为 3
 *              每次更新 max = max(max,stack.size())
 *
 * 2. 算法分析
 *
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 括号的最大嵌套深度 {
    public static void main(String[] args) {
        System.out.println(maxDepth("(1+(2*3)+((8)/4))+1"));
    }

    public static int maxDepth(String s) {
        int res = 0; // s的最大深度
        int cur = 0; // 当前的最大深度
        char[] arr = s.toCharArray();
        for(char c: arr){
            if(c == '(') cur ++; // 如果是'(',让cur++(此时的想法就是如果当前字符可以发生匹配，最大深度就是cur)
            if(c == ')') cur --; // 如果是')',让cur--(此时计算的就是实际深度，上面是理想的当前最大深度)
            res = Math.max(res,cur);
        }
        return res;
    }

    /**
     * 死循环
     * @param s
     * @return
     */
    public static int test(String s) {
        if(s.length() == 0 || s.length() == 1) {
            return 0;
        }
        int max = 0; // 用于记录s的最大深度
        Stack<Character> Stack = new Stack<>(); // 创建一个辅助栈
        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(') {
                Stack.add(s.charAt(i));
            } else {
                // 当前字符为')',开始出栈
                int cur = 0; // 设置一个变量记录当前的最大深度
                int j = i; // 从当前字符的下一个开始遍历
                while(j < s.length()) {
                    if(s.charAt(j) == ')') {
                        cur++;
                        j++;
                        if (!Stack.empty()) {
                            Stack.pop(); // 将匹配的'('出栈
                        }
                    } else {
                        break;
                    }
                }
                max = Math.max(cur,max);
            }
        }
        return max;
    }

    // 判断s的括号是否匹配
    public static boolean ismatch(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {

        }

        return true;
    }
}
